1. Field of the Invention
The present invention is directed generally to a method and apparatus for determining position and orientation of an object and, more particularly, to a method and apparatus for determining position and orientation of an object relative to a scene independent of infrastructure.
2. Description of the Background
High repeatability, position estimation is a key technology for mobile robotics applications such as seaport and manufacturing facility automation. Near term operations in those applications requires relatively precise positioning repeatabilities, such as, for example, approximately three millimeters. Three millimeters represents a significant improvement over the current industry standard of approximately five millimeters. The three millimeter repeatability must be achieved at an acceptable cost per unit. High end laser and inertial units are capable of meeting the technical specifications. However, their $20,000 to $100,000 plus per unit cost is far too high to be economically justifiable for most applications. Thus, a significant tradeoff exists between price and performance which prohibits flat floor mobile robotics companies from servicing existing demands in the market.
The least expensive positioning systems are so-called dead reckoning systems produced from low cost wheel encoders and a compass. Those systems produce an estimate of position based on the integration of rate measurements. Thus, they suffer from significant error accumulation in the estimate. High end dead reckoning systems, such as military grade inertial systems, reduce that problem by using rate sensors with very low error bias, but at a cost that is order of magnitudes higher than those acceptable to flat floor markets.
One low cost alternative is to combine the low cost dead reckoning system with a triangulation system, which can be used to reset the accumulated error by calculating a fix on the position. Triangulation systems do not perform integration, and thus are not affected by sensor bias. However, they suffer from dilution of precision problems that arise during the conversion of their measurements to the coordinate system of interest, e.g., a range and orientation of the sensor is converted to Cartesian space (xy). Triangulation systems take measurements with respect to external beacons or other items of infrastructure which make them vulnerable to sabotage. In certain industrial applications, sabotage is a key concern. Furthermore, the placement of beacons or other items of infrastructure represents a significant additional overhead cost to the end user. In certain applications, approximately one-third of the total cost of the system is due to the installation of beacons or other items of infrastructure.
Published German patent application DE 41 380 270 A discloses a method for the navigation of a self-propelled land vehicle in which markers are detected during travel, digitized and compared with stored data generated during a learning trip, in order to determine deviations from specified values whereby the deviations are processed into appropriate navigation control signals. The method is independent of artificial markers and ranges because natural landmarks are used as markers, which are captured as images by a video camera with two degrees of freedom. The actual position of the vehicle relative to a target point and the current vehicle direction in relation to the intended direction is calculated from the displacements of a pair of landmarks. Published European patent application EP 0 390 052 A discloses a landmark recognition system based on the perception, reasoning, action, and expectation (PREACTE) paradigm for the navigation of autonomous mobile robots. The system uses expectation to predict the appearance and disappearance of objects. The system also predicts the appearance of landmarks at different ranges and aspect angles, and uses map information to generate expectations of the scene. This system represents a classical solution, but suffers from problems associated with implementation and poor performance.
U.S. Pat. No. 4,847,769 entitled xe2x80x9cAutomated Vehicle Drift Correctionxe2x80x9d discloses a navigation system which carries out a dead reckoning calculation of the vehicles position based on inputs from sensors and the motion of a steering wheel in the preceding time interval. U.S. Pat. No. 5,307,278 entitled xe2x80x9cMethod Of Determining The Position Of A Vehicle, Arrangement For Determining The Position Of A Vehicle, As Well As A Vehicle Provided With Such An Arrangementxe2x80x9d, also relies upon dead reckoning.
U.S. Pat. No. 5,170,352 entitled xe2x80x9cMulti-Purpose Autonomous Vehicle With Path Plottingxe2x80x9d is an example of an autonomous vehicle which operates in conjunction with a plurality of laser, sonic, and optical sensors. Such sensors detect targets and obstacles in the work area and provide coded signals which direct vehicles over a most expedient route to a target while avoiding any obstacles.
U.S. Pat. No. 5,363,305 entitled xe2x80x9cNavigation System For A Mobile Robotxe2x80x9d discloses an apparatus for creating and maintaining a map of an environment the mobile autonomous robot is to transverse. A credibility measure is increased or decreased whenever a map feature assigned to a location matches or does not match, respectively, a geometric beacon corresponding to such location.
U.S. Pat. No. 4,979,113 entitled xe2x80x9cAutomated Vehicle Controlxe2x80x9d discloses a system in which data identifying locations of notational points on the floor of the area of interest are entered into a computer together with a look-up table specifying pairs of those points between which movements of vehicles may be required.
U.S. Pat. No. 4,847,773 entitled xe2x80x9cSystem For Navigating A Free-Ranging Vehiclexe2x80x9d discloses a system in which the surface to be traversed carries a grid of passive marker elements with the vehicle being provided with detectors for detecting such elements.
U.S. Pat. No. 4,647,784 entitled xe2x80x9cVehicle Guidance and Control Systemxe2x80x9d discloses a system in which vehicles determine their own position in relation to marker boards consisting of patterns of reflective coded strips by scanning a narrow laser beam in a predetermined direction across the strips. Positions can be determined by using triangulation.
U.S. Pat. No. 4,727,492 entitled xe2x80x9cVehicle Control And Guidance Systemxe2x80x9d discloses a vehicle guidance system which uses dead reckoning to predict the position of the vehicle. At the end of predetermined intervals, the dead reckoning is corrected by an independent fixed-target detection system using a scanning laser.
Other low cost alternatives are based on the use of vision systems to take range readings, e.g., stereo vision, of known features in an environment, such as doorways and room corners. A position is determined based on such readings. Although that method does not require the placement of infrastructure, it suffers from the significant problem of shape dependence. Briefly, what a feature looks like depends upon the angle from which it is viewed. That problem entails such computational complexity that commercially practical vision systems that operate on natural features have never been produced.
Thus, while substantial work has been directed at solving the aforementioned problems, it is seen from the prior art discussed above that such problems have not been solved. Many position determining systems are still dependent upon infrastructure which is expensive. Furthermore, once the infrastructure is in place, the facility can usually not be modified without the additional expense of modifying the infrastructure. Additionally, robots relying upon such infrastructure can easily be sabotaged.
Dead reckoning systems do not provide the repeatability required by today""s commercial application. Combining dead reckoning systems with some form of triangulation or other correction method introduces infrastructure, and all of the problems associated therewith.
Vision systems, which can provide higher accuracy than dead reckoning systems and which are typically free of artificially imposed infrastructure, are difficult and costly to implement. If a feature is unrecognizable because it is approached from a different angle, the robot may become disoriented and cease to function. Thus, the need exists for a position determining system which is highly accurate, independent of all infrastructure, relatively immune to sabotage, and which provides the high repeatability demanded in today""s marketplace at a competitive cost.
The present invention is directed to a computer-assisted method for determining a position and an orientation of a sensor relative to a scene. The sensor has a plurality of degrees of freedom in position and orientation relative to the scene. The method includes sensing an image of the scene, the sensed image having a plurality of regions such that a sum of degrees of independent constraint of the plurality of regions equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene, comparing the plurality of regions of the sensed image to a plurality of regions of a first image of the scene stored in a map, the first stored image representative of a position and orientation of the sensor relative to the scene, and determining sensor position and orientation based on the comparing.
The present invention represents an advancement over prior position determining systems because it does not require the use of infrastructure to determine position and orientation. The present invention also has the advantage that it obviates the need to compensate for the eventuality of local distortion of the regions of the scene. The present invention also has the advantage that it can provide robust and accurate estimations of sensor position and orientation. These and other advantages and benefits of the present invention will become apparent from the description hereinafter.